package com.wfs.suanfa.leet;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 广度优先搜索
 * @author wfs
 * @date 2022-11-14 9:36
 */
public class BreadthFirstSearch {

    public static void main(String[] args) {
        Graph graph=new Graph(8);
        graph.addEdge(0,1);
        graph.addEdge(0,3);
        graph.addEdge(1,2);
        graph.addEdge(1,4);
        graph.addEdge(2,5);
        graph.addEdge(3,4);
        graph.addEdge(4,5);
        graph.addEdge(4,6);
        graph.addEdge(5,7);
        graph.addEdge(6,7);
        graph.bfs(0,6);
    }

}


class Graph{
    /**
     * 顶点个数
     */
    private int v;
    /**
     * 邻接表
     */
    private LinkedList<Integer> adj[];
    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }
    // 无向图一条边存两次
    public void addEdge(int s, int t) {
        adj[s].add(t);
        adj[t].add(s);
    }

    /**
     * 图的广度优先搜索的代码实现
     * @param s 表示起始顶点，
     * @param t 表示终止顶点
     */
    public void bfs(int s,int t){
        if (s==t) return;
        //visited是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点q被访问，那相应的visited[q]会被设置为true。
        boolean[] visited = new boolean[v];
        visited[s]=true;
        //queue是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，
        //我们只有把第k层的顶点都访问完成之后，才能访问第k+1层的顶点。当我们访问到第k层的顶点的时候，我们需要把第k层的顶点
        // 记录下来，稍后才能通过第k层的顶点来找第k+1层的顶点。所以，我们用这个队列来实现记录的功能。
        Queue<Integer> queue=new LinkedList<>();
        queue.add(s);
        //prev用来记录搜索路径。当我们从顶点s开始，广度优先搜索到顶点t后，prev数组中存储的就是搜索的路径。不过，这个路径是
        // 反向存储的。prev[w]存储的是，顶点w是从哪个前驱顶点遍历过来的。比如，我们通过顶点2的邻接表访问到顶点3，那prev[3]就
        // 等于2。为了正向打印出路径，我们需要递归地来打印，你可以看下print()函数的实现方式。
        int[] prev=new int[v];
        for (int i = 0; i < v; i++) {
            prev[i]=-1;
        }
        while (queue.size() != 0) {
            int w = queue.poll();
            for (int i = 0; i < adj[w].size(); ++i) {
                int q = adj[w].get(i);
                if (!visited[q]) {
                    prev[q] = w;
                    if (q == t) {
                       print(prev, s, t);
                      return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }
    /**
     * 广度优先搜索 打印所有路径
     */
  /*  public void bfsAll(int s,int t){
        if (s==t)return;
        //记录扫描节点
        Queue<Integer> queue=new LinkedList();
        queue.add(s);
        *//*int[] prev=new int[v];
        for (int i = 0; i < v; i++) {
            prev[i]=-1;
        }*//*
        boolean visited[] =new boolean[v];
        visited[s]=true;
        List<Integer> list=new ArrayList<>();
        while (queue.size() != 0) {
            Integer poll = queue.poll();
            //获取该节点所有连线
            for (int i = 0; i < adj[poll].size(); i++) {
                //遍历连线
                Integer temp = adj[poll].get(i);
                if (visited[temp]){
                    continue;
                }
                if (temp==t){
                    System.out.println("1");
                  *//*  for (Integer integer : list) {
                        System.out.println(integer+" ");
                    }
                    System.out.println();*//*
                }else {
                    list.add(poll);
                    visited[temp]=true;
                    queue.add(temp);
                }
            }
        }
    }
*/

    /**
     * 递归打印s->t的路径
     * @param prev 搜索路径
     * @param s 表示起始顶点，
     * @param t 表示终止顶点
     */
    private void print(int[] prev, int s, int t) {
        if (prev[t] != -1 && t != s) {
            print(prev, s, prev[t]);
        }
        System.out.print(t + " ");
    }
    //当我们已经找到终止顶点t之后，我们就不再递归地继续查找了。
    boolean found;
    /**
     * 深度优先搜索
     * @param s 表示起始顶点，
     * @param t 表示终止顶点
     */
    public void dfs(int s, int t) {
        found = false;
        boolean[] visited = new boolean[v];
        int[] prev = new int[v];
        for (int i = 0; i < v; ++i) {
            prev[i] = -1;
        }
        recurDfs(s, t, visited, prev);
        print(prev, s, t);
    }

    private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
        if (found == true) return;
        visited[w] = true;
        if (w == t) {
            found = true;
            return;
        }
        for (int i = 0; i < adj[w].size(); ++i) {
            int q = adj[w].get(i);
            if (!visited[q]) {
                prev[q] = w;
                recurDfs(q, t, visited, prev);
            }
        }
    }
}
